/***尚硅谷Java数据结构与java算法                  ***/
/***https://www.bilibili.com/video/BV1E4411H73v ***/
/***迷宫问题    递归解法                         ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
using std::cout;
using std::endl;
//c++中不存在二维数组的概念，而是理解为是一个 一维数组的一维数组
bool setWay(int (*array)[7], int i, int j);
void printArray(const int (*array)[7]);

int main()
{
    int(*array) [7] =new int[8][7];
    for(int i=0;i<8;i++){
        for(int j=0;j<7;j++)
            array[i][j]=0;
    }
    for(int i=0;i<7;i++){
        array[0][i]=1;
        array[7][i]=1;
    }        
    for (int i = 0; i < 8; i++)
    {
        array[i][0]=1;
        array[i][6]=1;
    }
    array[3][1]=1;
    array[3][2]=1;
    cout<<"变幻之前的矩阵！"<<endl;
    printArray(array);
    setWay(array,1,1);
    cout<<"变幻之后的矩阵！"<<endl;
    printArray(array);
    delete array;
}

void printArray(const int (*array)[7])
{
    for(int i=0;i<8;i++){
        for(int j=0;j<7;j++){
            cout<<array[i][j]<<" ";
        }
        cout<<endl;
    }
}
/*
作用：迷宫递归用的计算函数
参数：array  地图， i,j  标注了迷宫的起始位置；
返回值：bool 返回正确或者错误；
array中 0代表未走过，1代表是墙，2代表是走过，3代表走过未走通；
走的规则是 下->右->上->左
*/
bool setWay(int (*array)[7], int i, int j)
{//如果[6][5]=2,代表走到了地图的重点；
    if (array[6][5]==2){
        return true;
    }
    else{
        if (array[i][j]==0){
            array[i][j]=2;
            if (setWay(array,i+1,j)){
                return true;
            }
            else if (setWay(array,i,j+1)){
                return true;
            }
            else if (setWay(array,i-1,j)){
                return true;
            }
            else if (setWay(array,i,j-1)){
                return true;
            }
            else {
                array[i][j]=3;
                return false;
            }
        }
        else {
            return false;
        }
    }
}